/* 
  快排实现（思想：分治和分区的概念进行递归操作）
  比如要对sort(arr, 0, arr.length - 1)的序号进行排序
  1 取一个数（一般是arr[right]）中位数
  2 然后遍历0- arr.length - 1 区间，将小于中位数的放在左边，大于中位数的放在右边
    当操作完之后，那么中位数（index）左边的就都是小于它的，右边的都是大于它。
  3 第二步操作完后，那么我们继续对中位数两边的区间进行第一、第二步操作
    即对sort(arr, 0, index - 1)和sort(arr, index + 1, arr.lenght - 1)进行操作
*/

function swap(arr, i, j) {
  const temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}

/**
 *
 *
 * @param {*} arr
 * @param {*} left
 * @param {*} right
 * @return 返回分区完成后，中位数的索引index
 */
function partition(arr, left, right) {
  console.log(left, right);
  const value = arr[right]; // 选取一个基点
  let partitionIndex = left;
  // j指针会一直遍历数组
  for(let j = left; j < right; j++) {
    // 当发现有小于中位数的元素，那么交换位置，并且partitionIndex指针前移
    if (arr[j] < value) {
      swap(arr, partitionIndex, j)
      partitionIndex++;
    }
  }
  // for循环之后left - partitionIndex - 1区间的都是小于基数arr[right]的值
  // 这时候只需要交换partitionIndex和right的值即可完成分区操作
  swap(arr, partitionIndex, right);
  return partitionIndex;
}

function _quickSort(arr, left, right) {
  // 说明只有已经分区到 <= 1个元素了 直接返回
  if (left >= right) return;

  const partitionIndex = partition(arr, left, right);
  _quickSort(arr, left, partitionIndex - 1);
  _quickSort(arr, partitionIndex + 1, right);
}
function quickSort(arr) {
  _quickSort(arr, 0, arr.length - 1);
}

const arr = [];
let i = 0;
while(i < 10) {
  arr.push(Math.floor(Math.random() * 100));
  i++;
}
console.log(arr);
console.log('------');
quickSort(arr)
console.log(arr);